package com.str.set;
public class ArraySet implements Set, Cloneable {

  // This set is represented as follows:
  // its members occupy members[0...card-1].
  private final int DEFAULT_SIZE = 10;    
  private Comparable[] array;    
  private int count;

// Constructor
  public ArraySet() {
    array = new Comparable[DEFAULT_SIZE];
    count = 0;
  }

// Modifiers
  public void clear() {
  	for (int i = 0; i < count; i++)
  	  array[i] = null;
  	count = 0;
  }
  
  public void add(Object val) {
  	Comparable item = (Comparable) val;
    int pos = search(item);
    if (! val.equals(array[pos])) {
      if (count == array.length) expand();
      for (int i = count; i > pos; i--)
        array[i] = array[i-1];
      array[pos] = item;
      count++;
    }
  }

  public Object remove(Object val) {
  	if (val instanceof Comparable) {
      int pos = search((Comparable) val);
      if (pos < count && val.equals(array[pos])) {
        Object temp = array[pos];
        for (int i = pos; i < count-1; i++)
          array[i] = array[i+1];
        array[--count] = null;
        return temp;
      }
    }
    return null;
  }

  public void union(Set that) {
    ArraySet other = (ArraySet) that;
    int len = array.length + other.array.length;
    Comparable[] newArray = new Comparable[len];
    int i = 0, j = 0, k = 0;
    while (i < count && j < other.count) {
      int comp = array[i].compareTo(other.array[j]);
      if (comp < 0)
        newArray[k++] = array[i++];
      else if (comp > 0)
        newArray[k++] = other.array[j++];
      else {   // if (comp == 0)
      	newArray[k++] = array[i++];  
        j++;
      }  
    }
    while (i < count)
      newArray[k++] = array[i++];
    while (j < other.count)
      newArray[k++] = other.array[j++];
    array = newArray;  
    count = k;
  }

  public void intersection(Set that) {
    ArraySet other = (ArraySet) that;
    Comparable[] newArray = new Comparable[array.length];
    int i = 0, j = 0, k = 0;    
    while (i < count && j < other.count) {
      int comp = array[i].compareTo(other.array[j]);
      if (comp < 0) i++;
      else if (comp > 0) j++;
      else {   // if (comp == 0)
        newArray[k++] = array[i++];  
        j++;
      }
    }
    array = newArray;  
    count = k;
  }

  public void difference(Set that) {
    ArraySet other = (ArraySet) that;
    Comparable[] newArray = new Comparable[array.length];
    int i = 0, j = 0, k = 0;
    while (i < count && j < other.count) {
      int comp = array[i].compareTo(other.array[j]);
      if (comp < 0)
        newArray[k++] = array[i++];
      else if (comp > 0)
        j++;
      else {  // if (comp == 0)
        i++;
        j++;
      }
    }
    while (i < count)
      newArray[k++] = array[i++];
    array = newArray;  
    count = k;
  }

// Accessors ...
  public boolean isEmpty()
  { return count == 0; }

  public int size()
  { return count; }

  public boolean contains(Object val) {
    if (val instanceof Comparable) {
      int pos = search((Comparable) val);  
      return val.equals(array[pos]);
    }
    else return false;
  }

  public boolean equals(Set that) {
    ArraySet other = (ArraySet) that;
    if (count != other.count)
      return false;
    for (int i = 0; i < count; i++)
      if (! array[i].equals(other.array[i]))
        return false;
    return true;
  }

  public boolean isSubset(Set that) {
    ArraySet other = (ArraySet) that;
    if (count > other.count)
      return false;
    int i = 0, j = 0;
    while (i < count && j < other.count) {
      int comp = array[i].compareTo(other.array[j]);
      if (comp < 0)
        return false;
      else if (comp > 0)
        j++;
      else {  // if (comp == 0)
        i++;  
        j++;
      }
    }
    return i == count;
  }

// Auxiliary methods  
  private int search(Comparable val) {
  // Return the index of the leftmost component of array
  // that is not less than val.
    int l = 0, r = count - 1;
    while (l <= r) {
      int m = (l + r) / 2;
      int comp = val.compareTo(array[m]);
      if (comp == 0)    // Here val is equal to array[m]. 
        return m;
      else if (comp < 0)
        r = m - 1;
      else l = m + 1;
    }
    // Here val is greater than array[0..l-1] and less than
    // array[l..count-1].
    return l;
  }
  
  public Object clone() {
    ArraySet that = new ArraySet();
    that.array = new Comparable[array.length];
    that.count = count;    
    for (int i = 0; i < count; i++)
      that.array[i] = array[i];
    return that;
  }

  private void expand() {
  	Comparable[] newArray = new Comparable[2 * array.length];
  	for (int i = 0; i < array.length; i++)
  	  newArray[i] = array[i];
  	array = newArray;
  }
  
  public String toString() {
    String buf = "{ ";
    for (int i = 0; i < count; i++) {
      if (i > 0)  buf += ", ";
        buf += array[i].toString();
    }
    buf += " }";
    return buf;
  }
}
